/*
A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?

Note: m and n will be at most 100.
*/

class Solution {
public:
    int uniquePaths(int m, int n) {
        int npaths[m+1][n+1];
        for (int i = 0; i <= n; i++) npaths[0][i] = 0;
        for (int i = 0; i <= m; i++) npaths[i][0] = 0;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <=n; j++) {
                if (i==1 && j==1) npaths[i][j] = 1;
                else npaths[i][j] = npaths[i-1][j] + npaths[i][j-1];
            }
        }
        return npaths[m][n];
    }
};

#if 0
class Solution {
public:
    int backtrack(int r, int c, int m, int n, int mat[][102]) {
        if (r == m && c == n)
            return 1;
        if (r > m || c > n)
            return 0;
 
        if (mat[r+1][c] == -1)
            mat[r+1][c] = backtrack(r+1, c, m, n, mat);
        if (mat[r][c+1] == -1)
            mat[r][c+1] = backtrack(r, c+1, m, n, mat);
 
        return mat[r+1][c] + mat[r][c+1];
    }
    int uniquePaths(int m, int n) {
        int mat[100+2][100+2];
        for (int i = 0; i < 102; i++) {
            for (int j = 0; j < 102; j++) {
                mat[i][j] = -1;
            }
        }
        return backtrack(1, 1, m, n, mat);       
    }
};
#endif
